package com.chengzhi.structure;

/**
 * 红黑树特性
 * <p>
 * 1.每个节点有可能是红色或者黑色
 * 2.根节点是黑色的
 * 3.每一个叶子节点（最后的空节点）是黑色的
 * 4.如果一个节点是红色的，那么它的孩子节点都是黑色的。
 * 5.从任意一个节点到叶子节点的，经过的黑色节点是一样多的。
 * <p>
 * 基于黑色平衡的二叉树
 *
 * @description: red-black-tree
 * @author: ruanchengzhi
 * @create: 2020-03-18 17:02
 **/
public class RBTree<K extends Comparable<K>, V> {

    private static final boolean RED = true;
    private static final boolean BLACK = true;
    private Node root;
    private int size;

    public RBTree(){
        root = null;
        size = 0;
    }

    public void add(K key, V value) {
        root = add(root, key, value);
        root.color = BLACK;
    }

    /**
     * 1  插入节点是根节点
     *
     * @param node
     * @param key
     * @param value
     * @return: com.chengzhi.structure.RBTree<K, V>.Node
     * @author: ruanchengzhi
     * @date: 2020/3/19
     */
    private Node add(Node node, K key, V value) {
        if (null == node) {
            size++;
            return new Node(key, value);
        }
        if (key.compareTo(node.key) > 0) {
            node.right = add(node.right, key, value);
        } else if (key.compareTo(node.key) < 0) {
            node.left = add(node.left, key, value);
        } else {
            node.value = value;
        }
        ///左旋转：右孩子是红色，左孩子是黑色
        if (isRed(node.right) && !isRed(node.left)){
            node = leftRotate(node);
        }
        //右旋转：左孩子是红节点，左孩子的左孩子是红节点
        if (isRed(node.left) && isRed(node.left.left)){
            node = rightRotate(node);
        }
        //颜色翻转：左右节点都是红色
        if (isRed(node.left) && isRed(node.right)){
            flipColors(node);
        }
        return node;
    }

    // 颜色翻转
    private void flipColors(Node node){
        node.color = RED;
        node.left.color = BLACK;
        node.right.color = BLACK;
    }

    private boolean isRed(Node node) {
        if (node == null) {
            return BLACK;
        }
        return node.color;
    }
    //
    // 对节点y进行向左旋转操作，返回旋转后新的根节点x
    //  node                           x
    //  /  \                          /
    // T1   x      向左旋转 (y)     node
    //     /    - - - - - - - ->   / \
    //   T2                       T1 T2
    private Node leftRotate(Node node) {
        Node x = node.right;
        node.right = x.left;
        x.left = node;
        x.color = node.color;
        node.color = RED;
        return x;
    }


    //     node                   x
    //    /   \     右旋转       /  \
    //   x    T2   ------->   y   node
    //  / \                       /  \
    // y  T1                     T1  T2
    private Node rightRotate(Node node) {
        Node x = node.left;
        // 右旋转
        node.left = x.right;
        x.right = node;
        x.color = node.color;
        node.color = RED;
        return x;
    }


    public Node delete(K key) {
        return null;
    }


    class Node {
        K key;
        V value;
        Node left;
        Node right;
        boolean color;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
            color = RED;
        }
    }
}
